#ifndef AI_SEARCH_MT_H
#define AI_SEARCH_MT_H



#include "ai.h"



class sa_worker;



/** @brief Class for comfortable handling of QReadWriteLock.
*
*	The QReadWriteLock is locked when class is created and unlocked, when it is destructed
*
*   \image html ai_search_mt.jpeg
*/
class QRWLocker
{

public:

	/** @brief Constructor locks QReadWriteLock
	*	@param lck QReadWriteLock to lock
	*	@param lock_write if QReadWriteLock will be locked for writing, or only for reading
	*/
	QRWLocker( QReadWriteLock *lck, bool lock_write )
	{
		rwlock = lck;
		if ( lock_write )
		{
			rwlock->lockForWrite();
			lock_type = 2;
		}
		else
		{
			rwlock->lockForRead();
			lock_type = 1;
		}
	};

	//! @brief Destructor unlocks QReadWriteLock
	~QRWLocker()
	{
		if ( lock_type > 0 )
			rwlock->unlock();
		lock_type = 0;
	};

	//! @brief Unlocks QReadWriteLock
	void unlock()
	{
		if ( lock_type > 0 )
			rwlock->unlock();
		lock_type = 0;
	};

	/** @brief Locks QReadWriteLock
	*	@param lock_write if QReadWriteLock will be locked for writing, or only for reading
	*/
	void relock( bool lock_write )
	{
		if ( lock_type > 0 )
			return;

		if ( lock_write )
		{
			rwlock->lockForWrite();
			lock_type = 2;
		}
		else
		{
			rwlock->lockForRead();
			lock_type = 1;
		}
	};

	//! @brief Locks QReadWriteLock for write if locked for read
	void raise_lock()
	{
		if ( lock_type != 1 )
			return;
		rwlock->unlock();
		lock_type = 0;
		rwlock->lockForWrite();
		lock_type = 2;
	};


private:

	//! QReadWriteLock to handle
	QReadWriteLock* rwlock;
	//! how the lock is locked: 0 -> unlocked, 1 -> locked for read, 2 -> locked for write
	unsigned short lock_type;

};



/** @brief AI state, that is used to build a search multi_threaded
*
*   \image html ai_search_mt.jpeg
*/
class ai_states_node_mt
{

public:

	/**	@brief Constructor, that connects ai_game_state to states tree
	*	@param p parrent of the node
	*	@param s ai_game_state to be connected to the parent
	*/
	ai_states_node_mt( ai_states_node_mt* p, ai_game_state* s );

	//! @brief Destructor deletes all its children
	~ai_states_node_mt();

	//! algorithm owner's score
	double my_score;
	//! current player's score
	double current_score;
	//! previous player's score
	double prev_score;

	//! parent of this node
	ai_states_node_mt* parent;
	//! parent of this node at the end of previous level
	ai_states_node_mt* level_parent;
	//! list of children
	list< ai_states_node_mt* >* children;
	//! list of children at the beginning of next level
	list< ai_states_node_mt* >* level_children;
	//! the ai_game_state
	ai_game_state* state;
	//! actual depth, where the node is
	int depth;

	//! lock for syncing threads for level_children
	QReadWriteLock* lock_level_children;

	/** @brief Adds child to level children list (thread safe)
	*	@param lev_child
	*/
	void add_level_children( ai_states_node_mt* lev_child );
};



/** @brief The main algorithm class.
*
*	This algorithm is based on search of state space and generating state tree. The whole state space is being searched to depth set in
*	parameters::ai_parameters[ "SEARCH_MT" ][ "depth" ]. Depth 1 means, that the state space will be searched to the end of first player's turn.
*	Depth 2 means, that it will be searched to the end of next player's turn and so on.
*
*	Before the algorithm starts, it determines, how many threads it can run, so that the computer will be utilised optimally.
*	At the beginning, the given game_state is used to create the root of whole tree composed of ai_states_node_mt. For each ation, that can be done
*	on the node, the child is added. When there are less threads running, than optimal number is, new thread will be fork and the child will
*	be processed here. When the child contains "NXT" command, it is connected to ai_states_node_mt::level_parent. Duplicities are
*	excluded using search_algorithm::searched_states_list. All accesses to shared variables are treated by QReadWriteLock and QRWLocker classes.
*
*	At the end of search, we find the best commands. We assume, that every players is maximising his score and thinks one round to future,
*	so we search only states in mt_search_algorithm::state_levels and when the enemy is on turn, we find for each child the one with maximum score
*	and we assume, that he will choose this state. The previous player is trying to avoid this player to maximise his score, so he will choose
*	the state, where his worst predictabe score is highest nad so on. When we get to root, we find the state with highest score for us and find
*	commands, how to get there.
*
*   \image html ai_search_mt.jpeg
*/
class mt_search_algorithm: public algorithm
{

public:

	//! @brief Constructor only assignes the name
	mt_search_algorithm();

	//! @brief Destructor cleans all staff
	~mt_search_algorithm();
	

	/** @brief	Registrating function (adds ai algorithm to map)
	*/
	static void register_me()
	{
		register_metpl< mt_search_algorithm >();
	};

	/** @brief	Cloning function for init purposes
	*	@return	clone of the algorithm
	*/
	virtual algorithm* clone()
	{
		mt_search_algorithm* cl = clonetpl< mt_search_algorithm >();
		return cl;
	};

	/** @brief Function called at the beginning of buy
	*	@param gs current game state
	*/
	virtual void get_buy_commands( const game_state* gs );
	/** @brief Function called at the beginning of every turn
	*	@param gs current game state
	*/
	virtual void get_commands( const game_state* gs );

	/** @brief Adds given values to nodes_to_search and searched_nodes and prints result (thread safe)
	*	@param nts value for changing nodes_to_search
	*	@param sn value for changing searched_nodes
	*/
	void change_nodes_counters( int nts, int sn );
	/** @brief Adds given state to state_levels list (thread safe)
	*	@param state_node state to push into the list
	*/
	void add_to_state_levels( ai_states_node_mt* state_node );
	/** @brief Adds state to list of searched states (thread safe)
	*	@param state game state to add, constraint: state != 0
	*/
	void add_to_list( game_state* state );
	/** @brief	Checks if the state was already searched (thread safe)
	*	@param	state game state to check, constraint: state != 0
	*	@return true if state is already in list and was searched, else false
	*/
	bool is_in_list ( game_state* state );
	//! @brief Increases thread counter for purposes of forking new threads (thread safe)
	void thread_started();
	//! @brief Decreases thread counter for purposes of forking new threads (thread safe)
	void thread_finished();
	/** @brief Adds worker to list (thread safe)
	*	@param worker worker to add
	*/
	void add_worker( sa_worker* worker );
	//! @brief Clears finished tasks from list (thread safe)
	void clear_workers();
	/** @brief	Checks if there are enough running threads (thread safe)
	*	@return true if more thread should be forked, else false
	*/
	bool fork_new_thread();
	/** @brief	Checks if there are some working workers remaining (thread safe)
	*	@return true if there are working threads, else false
	*/
	bool exist_reamaining_nodes();

	//! given state - never changed
	const game_state* original_state;


private:

	//! list of workers
	list< sa_worker* >* workers;

	//! pointer to the root of the tree
	ai_states_node_mt* search_tree;

	//! map of searched states, indexed by hash, one field contains list of states with same hash
	map< unsigned long long int, list< game_state* > >* searched_states_list;

	//! vector of lists, where are all states in one depth, that are on the end of turn
	vector< list< ai_states_node_mt* > >* state_levels;

	/** @brief	Finds form list of nodes the one with highest score for algorithm owner
	*	@param	node_list list where to find for the node
	*	@return	node with the highest score
	*/
	ai_states_node_mt* find_max_score_me( list< ai_states_node_mt* >* node_list );
	/** @brief	Finds form list of nodes the one with highest score for current player
	*	@param	node_list list where to find for the node
	*	@return	node with the highest score
	*/
	ai_states_node_mt* find_max_score_curr( list< ai_states_node_mt* >* node_list );
	/** @brief	Finds form list of nodes the one with highest score for previous player
	*	@param	node_list list where to find for the node
	*	@return	node with the highest score
	*/
	ai_states_node_mt* find_max_score_prev( list< ai_states_node_mt* >* node_list );

	//! remaining nodes to search
	unsigned int* nodes_to_search;
	//! searched nodes
	unsigned int* searched_nodes;
	//! currently running threads
	unsigned int* running_threads;

	//! lock for syncing threads for state_levels
	QReadWriteLock* lock_levels_list;
	//! lock for syncing threads for searched_states_list
	QReadWriteLock* lock_searched_states_list;
	//! lock for syncing threads for nodes_to_search and searched_nodes
	QReadWriteLock* lock_counters;
	//! lock for syncing threads for running_threads
	QReadWriteLock* lock_thread_counter;
	//! lock for syncing threads for workers list
	QReadWriteLock* lock_workers_list;

};



/** @brief Thread for expanding one node.
*
*   \image html ai_search_mt.jpeg
*/
class sa_worker: public QThread
{

public:

	/** @brief Constructor sets the main algorithm for syncing and state node for expanding
	*	@param msa main algorithm for syncing
	*	@param state_node state node for expanding
	*	@param parent Qt parent
	*/
	sa_worker( mt_search_algorithm* msa, ai_states_node_mt* state_node, QObject* parent = 0 ): QThread( parent )
	{
		my_search_tree = state_node;
		main_mt_sa = msa;
		setTerminationEnabled ( false );
		main_mt_sa->add_worker( this );
		main_mt_sa->clear_workers();
	};

	//! @brief Destructor does nothing
	~sa_worker()
	{};

	//! @brief The starting point for the thread
	void run()
	{
		main_mt_sa->thread_started();
		search_state( my_search_tree );
		main_mt_sa->thread_finished();
	};



private:

	/**	@brief Expands given state and connects all children
	*	@param state_node node to expand, constraint: state_node != 0
	*/
	void search_state( ai_states_node_mt* state_node );

	//! root of ai_states_node subtree
	ai_states_node_mt* my_search_tree;
	//! pointer to main algorithm for syncing
	mt_search_algorithm* main_mt_sa;

};



#endif